package leetcode.editor.cn;
//二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。
// 
//
// 
// 例如，下面的二进制手表读取 "4:51" 。 
// 
//
// 
//
// 给你一个整数 turnedOn ，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。 
//
// 小时不会以零开头： 
//
// 
// 例如，"01:00" 是无效的时间，正确的写法应该是 "1:00" 。 
// 
//
// 分钟必须由两位数组成，可能会以零开头： 
//
// 
// 例如，"10:2" 是无效的时间，正确的写法应该是 "10:02" 。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：turnedOn = 1
// 0000
// 000000
//输出：["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]
// 
//
// 示例 2： 
//
// 
//输入：turnedOn = 9
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 0 <= turnedOn <= 10 
// 
//
// Related Topics 位运算 回溯 👍 423 👎 0


import java.util.LinkedList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution204 {
    // 点亮哪个位置，当前时间加上对应值
    int[] hours = new int[]{1, 2, 4, 8, 0, 0, 0, 0, 0, 0};
    int[] minutes = new int[]{0, 0, 0, 0, 1, 2, 4, 8, 16, 32};
    List<String> res = new LinkedList<>();

    public List<String> readBinaryWatch(int num) {
        backtrack(num, 0, 0, 0);
        return res;
    }

    /**
     * @param num    剩余需要点亮的灯数量，
     * @param index  从索引index开始往后点亮灯，
     * @param hour   当前小时数，
     * @param minute 当前分钟数
     */
    public void backtrack(int num, int index, int hour, int minute) {
        if (hour > 11 || minute > 59)
            return;
        if (num == 0) {
            StringBuilder sb = new StringBuilder();
            sb.append(hour).append(':');
            if (minute < 10) {
                sb.append('0');
            }
            sb.append(minute);
            res.add(sb.toString());
            return;
        }
        for (int i = index; i < 10; i++) {
            backtrack(num - 1, i + 1, hour + hours[i], minute + minutes[i]);
        }
    }


    /**
     * 当 时针代表的二进制中 1 的个数 + 分针所代表的二进制中 1 的个数 等于 num 时，即为本题的一个有效答案。
     * @param num
     * @return
     */
    public List<String> readBinaryWatch1(int num) {
        List<String> res = new LinkedList<>();

        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 60; j++) {
                int cnt = Integer.bitCount(i) + Integer.bitCount(j);
                if (cnt == num) {
                    // res.add(String.format("%d:%02d", i, j));
                    StringBuilder sb = new StringBuilder();
                    sb.append(i).append(':');
                    if (j < 10) {
                        sb.append('0');
                    }
                    sb.append(j);
                    res.add(sb.toString());
                }
            }
        }

        return res;
    }


    private int countOne(int num) {
        int cnt = 0;

        while (num > 0) {
            if ((num & 1) == 1) {
                cnt++;
            }
            num >>= 1;
        }

        return cnt;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
